Proč je zpracování seřazeného pole rychlejší než zpracování netříděného pole?

Jste obětí selhání predikce větve.
Co je Predikce větve?
Zvažte železniční křižovatku:
Obrázek Mecanismo, přes Wikimedia Commons. Používá se na základě licence CC-By-SA 3.0.
Nyní kvůli hádce předpokládejme, že je to zpět v 19. století - před dálkovou nebo rádiovou komunikací.
Jste obsluhou křižovatky a uslyšíte přijíždějící vlak. Netušíte, kterým směrem se má ubírat. Zastavíte vlak a zeptáte se řidiče, kterým směrem chtějí. A pak vhodně nastavíte přepínač.
Vlaky jsou těžké a mají velkou setrvačnost. Nastartování a zpomalení tedy trvá věčnost.
Existuje lepší způsob? Hádáte, kterým směrem se vlak vydá!
Pokud jste uhodli správně, pokračuje dál.
Pokud jste uhodli špatně, kapitán se zastaví, zacouvá a křičí na vás, abyste přepnuli spínač. Pak může restartovat druhou cestu.
Pokud uhodnete pokaždé, vlak nikdy nebude muset zastavit. Pokud příliš často hádáte špatně, vlak stráví spoustu času zastavováním, couváním a restartováním.
Zvažte příkaz if: Na úrovni procesoru je to instrukce větve:
Jste procesor a vidíte větev. Netušíte, kterým směrem se to bude ubírat. Co děláš? Zastavíte provádění a počkáte, dokud nebudou dokončeny předchozí pokyny. Pak budete pokračovat po správné cestě dolů.
Moderní procesory jsou komplikované a mají dlouhé kanály. „Zahřátí“ a „zpomalení“ jim tedy trvá věčnost.
Existuje lepší způsob? Hádáte, kterým směrem se bude větev ubírat!
Pokud jste uhodli správně, pokračujete v provádění.
Pokud jste uhodli špatně, musíte propláchnout potrubí a vrátit se zpět na větev. Poté můžete restartovat druhou cestu.
Pokud pokaždé hádáte správně, poprava se nikdy nebude muset zastavit. Pokud příliš často hádáte špatně, strávíte spoustu času zdržováním, vrácením zpět a restartováním.
Toto je predikce větve. Přiznávám, že to není nejlepší analogie, protože vlak mohl jen signalizovat směr vlajkou. Ale v počítačích procesor neví, kterým směrem se bude větev ubírat, až do poslední chvíle.
Jak byste tedy strategicky hádali, abyste minimalizovali počet případů, kdy musí vlak couvat a jít druhou cestou? Podíváte se na minulou historii! Pokud vlak jede 99% času doleva, pak hádáte doleva. Pokud se to střídá, pak střídáte své odhady. Pokud to jde jednou za cestu třikrát, hádáte to samé ...
Jinými slovy, pokusíte se identifikovat vzor a následovat ho. Takto víceméně fungují prediktory větví.
Většina aplikací má dobře vychované větve. Moderní větvové prediktory tedy obvykle dosáhnou> 90% úspěšnosti. Ale když se setkáme s nepředvídatelnými větvemi bez rozpoznatelných vzorů, prediktory větví jsou prakticky k ničemu.
Další čtení: Článek „Branch prediktor“ na Wikipedii.
Jak bylo naznačeno výše, viníkem je toto prohlášení if:
if (data [c]> = 128)
součet + = data [c];
Všimněte si, že data jsou rovnoměrně rozložena mezi 0 a 255. Když jsou data tříděna, zhruba první polovina iterací nezadá příkaz if. Poté všichni zadají příkaz if.
To je velmi přátelské k prediktoru větve, protože větev jde mnohokrát stejným směrem. I jednoduchý čítač nasycení správně předpovídá větev, kromě několika iterací po přepnutí směru.
Rychlá vizualizace:
T = větev přijata
N = větev není přijata
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
větev = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (snadno předvídatelné)
Když jsou však data zcela náhodná, prediktor větve se stane nepoužitelným, protože nemůže předpovídat náhodná data. Pravděpodobně tedy bude asi 50% chybná předpověď (o nic lepší než náhodné hádání).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
větev = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (zcela náhodné - těžko předvídatelné)
Co se tedy dá dělat?
Pokud kompilátor není schopen optimalizovat větev na podmíněný tah, můžete zkusit nějaké hacky, pokud jste ochotni obětovat čitelnost výkonu.
Nahradit:
if (data [c]> = 128)
součet + = data [c];
s:
int t = (data [c] - 128) >> 31;
součet + = ~ t & data [c];
To eliminuje větev a nahradí ji některými bitovými operacemi.
(Upozorňujeme, že tento hack není striktně ekvivalentní původnímu příkazu if. Ale v tomto případě je platný pro všechny vstupní hodnoty dat [].)
Srovnávací testy: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - vydání x64
// Pobočka - náhodná
sekund = 11,777
// Pobočka - seřazeno
sekund = 2,352
// Branchless - Random
sekund = 2,564
// Branchless - Sorted
sekund = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Pobočka - náhodná
sekund = 10,93293813
// Pobočka - seřazeno
sekund = 5,643797077
// Branchless -Náhodný
sekund = 3,113581453
// Branchless - Sorted
sekund = 3,186068823
Postřehy:
S pobočkou: Mezi seřazenými a netříděnými daty je obrovský rozdíl.
S hackem: Mezi seřazenými a netříděnými daty není žádný rozdíl.
V případě C ++ je hack ve skutečnosti o něco pomalejší než u větve, když jsou data tříděna.
Obecným pravidlem je zabránit větvení závislým na datech v kritických smyčkách (například v tomto příkladu).
Aktualizace:
GCC 4.6.1 s -O3 nebo -ftree-vectorize na x64 je schopen generovat podmíněný tah. Mezi seřazenými a netříděnými daty tedy není žádný rozdíl - obě jsou rychlé.
(Nebo poněkud rychle: pro již seřazený případ může být cmov pomalejší, zejména pokud jej GCC umístí na kritickou cestu místo pouhého přidání, zejména na Intel před Broadwell, kde cmov má latenci 2 cyklu: optimalizační příznak gcc -O3 zpomaluje kód než -O2)
VC ++ 2010 není schopen generovat podmíněné pohyby pro tuto větev ani pod / Ox.
Intel C ++ Compiler (ICC) 11 dělá něco zázračného. Zaměňuje dvě smyčky, čímž zvedá nepředvídatelnou větev do vnější smyčky. Je tedy nejen imunní vůči nesprávným předpovědím, ale také dvakrát rychlejší než cokoli, co dokáže generovat VC ++ a GCC! Jinými slovy, ICC využilo testovací smyčky k překonání měřítka ...
Pokud dáte kompilátoru Intel bezvětvový kód, jednoduše jej vektorizuje ... a je stejně rychlý jako u větve (s výměnou smyčky).
To ukazuje, že i vyspělé moderní kompilátory se mohou divoce lišit ve své schopnosti optimalizovat kód ...
|
Větev predikce.
U tříděného pole je podmínková data [c]> = 128 nejprve nepravdivá pro řadu hodnot, poté se stane pravdivou pro všechny pozdější hodnoty. To je snadné předvídat. U netříděného pole platíte náklady na větvení.
|
Důvodem, proč se výkon drasticky zlepšuje, když jsou data tříděna, je to, že trest predikce větve je odstraněn, jak je krásně vysvětleno v odpovědi Mysticial.
Nyní, když se podíváme na kód
if (data [c]> = 128)
součet + = data [c];
můžeme zjistit, že význam tohoto konkrétního, pokud ... else ... větev je přidat něco, když je podmínka splněna. Tento typ větve lze snadno transformovat na příkaz podmíněného přesunu, který by byl zkompilován do instrukce podmíněného přesunu: cmovl, v systému x86. Větev a tím i potenciální trest predikce větve je odstraněn.
V jazyce C, tedy C ++, je příkaz, který by se zkompiloval přímo (bez jakékoli optimalizace) do instrukce podmíněného pohybu v x86, ternárním operátorem ...? ...: .... Takže přepíšeme výše uvedené tvrzení na ekvivalentní:
součet + = data [c]> = 128? data [c]: 0;
Při zachování čitelnosti můžeme zkontrolovat faktor zrychlení.
Na Intel Core i7-2600K @ 3,4 GHz a režimu vydání Visual Studio 2010 je měřítko (formát zkopírovaný z Mysticial):
x86
// Pobočka - náhodná
sekund = 8 885
// Pobočka - seřazeno
sekund = 1,528
// Branchless - Random
sekund = 3,716
// Branchless - Sorted
sekund = 3,71
x64
// Pobočka - náhodná
sekund = 11,302
// Pobočka - seřazeno
sekund = 1,830
// Branchless - Random
sekund = 2,736
// Branchless - Sorted
sekund = 2,737
Výsledek je robustní v několika testech. Dostaneme skvělé zrychlení, když je výsledek větve nepředvídatelný, ale trochu trpíme, když je to předvídatelné. Ve skutečnosti je při použití podmíněného pohybu výkon stejný bez ohledu na vzor dat.
Podívejme se nyní blíže zkoumáním sestavení x86, které generují. Pro zjednodušení používáme dvě funkce max1 a max2.
max1 používá podmíněnou větev, pokud ... else ...:
int max1 (int a, int b) {
pokud (a> b)
vrátit a;
jiný
návrat b;
}
max2 používá ternární operátor ...? ...: ...:
int max2 (int a, int b) {
vrátit a> b? a: b;
}
Na stroji x86-64 generuje GCC -S níže uvedenou sestavu.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
odejít
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
odejít
ret
max2 používá mnohem méně kódu kvůli použití instrukce cmovge. Skutečným ziskem však je, že max2 nezahrnuje skoky větví, jmp, které by měly výrazný výkonnostní trest, pokud by předpovídaný výsledek nebyl správný.
Proč tedy podmíněný pohyb funguje lépe?
V typickém procesoru x86 je provedení instrukce rozděleno do několika fází. Zhruba máme jiný hardware, který se vypořádá s různými fázemi. Takže nemusíme čekat na dokončení jedné instrukce, abychom zahájili novou. Tomu se říká pipelining.
V případě větve je následující instrukce určena předchozí, takže nemůžeme provést pipeline. Musíme buď počkat, nebo předpovědět.
V případě podmíněného pohybuinstrukce podmíněného pohybu je rozdělena do několika fází, ale dřívější fáze jako Fetch a Decode nezávisí na výsledku předchozí instrukce; pouze poslední fáze vyžadují výsledek. Čekáme tedy zlomek času provedení jedné instrukce. To je důvod, proč je verze podmíněného pohybu pomalejší než větev, když je předpověď snadná.
Kniha Computer Systems: A Programmer's Perspective, druhé vydání, to podrobně vysvětluje. Můžete zkontrolovat část 3.6.6 s pokyny pro podmíněný přesun, celou kapitolu 4 o architektuře procesoru a část 5.11.2 se zvláštním zacházením s tresty předpovědi větve a nesprávné předpovědi.
Někdy mohou některé moderní kompilátory optimalizovat náš kód na sestavení s lepším výkonem, někdy některé kompilátory nemohou (dotyčný kód používá nativní kompilátor Visual Studio). Znalost rozdílu výkonu mezi větví a podmíněným pohybem, když je nepředvídatelný, nám může pomoci napsat kód s lepším výkonem, když se scénář stane tak složitým, že je kompilátor nemůže automaticky optimalizovat.
|
Pokud vás zajímá ještě více optimalizací, které lze u tohoto kódu provést, zvažte toto:
Počínaje původní smyčkou:
pro (nepodepsané i = 0; i <100000; ++ i)
{
for (unsigned j = 0; j  = 128)
součet + = data [j];
}
}
Při výměně smyčky můžeme tuto smyčku bezpečně změnit na:
for (unsigned j = 0; j  = 128)
součet + = data [j];
}
}
Pak můžete vidět, že podmínka if je konstantní po celou dobu provádění smyčky i, takže můžete zvednout if out:
for (unsigned j = 0; j  = 128)
{
pro (nepodepsané i = 0; i <100000; ++ i)
{
součet + = data [j];
}
}
}
Potom uvidíte, že vnitřní smyčku lze sbalit do jediného výrazu za předpokladu, že to model s plovoucí desetinnou čárkou umožňuje (například / fp: rychle je vyvolána)
for (unsigned j = 0; j  = 128)
{
součet + = data [j] * 100000;
}
}
Ten je stotisíckrát rychlejší než dříve.
|
Někteří z nás by bezpochyby měli zájem o způsoby identifikace kódu, který je problematický pro větvový prediktor CPU. Nástroj Valgrind cachegrind má simulátor větvového prediktoru, který je povolen pomocí příznaku --branch-sim = yes. Spuštěním v příkladech v této otázce s počtem vnějších smyček sníženým na 10 000 a kompilovaným s g ++ získáte tyto výsledky:
Seřazeno:
== 32551 == Pobočky: 656 645 130 (656 609 208 kond + 35 922 ind)
== 32551 == nesprávné předpovědi: 169 556 (169 095 kond + 461 ind)
== 32551 == Míra předpovědi: 0,0% (0,0% + 1,2%)
Netříděné:
== 32555 == Pobočky: 655 996 082 (65 5960 160 kond + 35 922 ind)
== 32555 == Špatné předpovědi: 164 073 152 (164072 692 podmínek + 460 ind)
== 32555 == Špatná sazba: 25,0% (25,0% + 1,2%)
Po přechodu do výstupu řádek po řádku produkovaném cg_annotate vidíme pro danou smyčku:
Seřazeno:
Bc Bcm Bi Bim
10 001 4 0 0 pro (nepodepsané i = 0; i <10 000; ++ i)
. . . . {
. . . . // primární smyčka
327 690 000 10 016 0 0 pro (nepodepsané c = 0; c  = 128)
0 0 0 0 součet + = data [c];
. . . . }
. . . . }
Netříděné:
Bc Bcm Bi Bim
10 001 4 0 0 pro (nepodepsané i = 0; i <10 000; ++ i)
. . . . {
. . . . // primární smyčka
327 690 000 10 038 0 0 pro (nepodepsané c = 0; c  = 128)
0 0 0 0 součet + = data [c];
. . . . }
. . . . }
To vám umožní snadno identifikovat problematický řádek - v netříděné verzi způsobí řádek if (data [c]> = 128) 164 050 007 chybně předvídaných podmíněných větví (Bcm) v modelu prediktoru větve cachegrind, zatímco ve tříděné verzi způsobí pouze 10 006 .
Alternativně v Linuxu můžete ke splnění stejného úkolu použít subsystém čítače výkonu, ale s nativním výkonem pomocí čítačů CPU.
stat stat ./sumtest_sorted
Seřazeno:
Statistiky čítače výkonu pro './sumtest_sorted':
11808.095776 task-clock # 0,998 využitých procesorů
1 062 kontextových přepínačů # 0,090 K / s
14 migrací CPU # 0,001 K / s
337 chyb stránek # 0,029 K / s
26 487 882 764 cyklů # 2,243 GHz
41025654322 pokynů # 1,55 insns za cyklus
6 558 871 379 poboček # 555 455 M / s
567 204 poboček chybí # 0,01% všech poboček
Uplynul čas 11,827228330 sekund
Netříděné:
Výkonstatistiky počítadla pro './sumtest_unsorted':
28877,954344 task-clock # 0,998 využitých procesorů
2 584 kontextových přepínačů # 0,089 K / s
18 migrací CPU # 0,001 K / s
335 chyb stránek # 0,012 K / s
65 076 127 595 cyklů # 2,253 GHz
41 032 528 741 pokynů # 0,63 insns za cyklus
6 560 579 013 poboček # 227,183 M / s
1 646 394 749 poboček chybí # 25,10% všech poboček
Uplynul čas 28,935500947 sekund
Může také provádět anotaci zdrojového kódu s demontáží.
záznam o rekordu -e větev chybí ./sumtest_unsorted
poznámka k perf -d sumtest_unsorted
Procenta Zdrojový kód a demontáž sumtest_unsorted
------------------------------------------------
...
: součet + = data [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39,97: 400 ald: mov% eax,% eax
5,31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: přidat% rax, -0x30 (% rbp)
...
Další podrobnosti najdete v tutoriálu výkonu.
|
Právě jsem si přečetl tuto otázku a její odpovědi a mám pocit, že odpověď chybí.
Běžným způsobem, jak eliminovat predikci větve, o které jsem zjistil, že funguje obzvlášť dobře ve spravovaných jazycích, je vyhledání tabulky namísto použití větve (i když jsem to v tomto případě netestoval).
Tento přístup funguje obecně, pokud:
je to malý stolek a pravděpodobně bude uložen do mezipaměti v procesoru, a
běžíte věci v poměrně těsné smyčce a / nebo procesor může předem načíst data.
Pozadí a proč
Z pohledu procesoru je vaše paměť pomalá. Aby se vyrovnal rozdíl v rychlosti, je do vašeho procesoru zabudováno několik mezipamětí (mezipaměť L1 / L2). Představte si tedy, že děláte pěkné výpočty a zjistíte, že potřebujete kus paměti. Procesor získá operaci „načtení“ a načte část paměti do mezipaměti - a poté použije mezipaměť k provedení zbývajících výpočtů. Protože paměť je relativně pomalá, toto „načtení“ zpomalí váš program.
Stejně jako predikce větve to bylo optimalizováno v procesorech Pentium: procesor předpovídá, že potřebuje načíst část dat, a pokusí se je načíst do mezipaměti, než operace skutečně zasáhne mezipaměť. Jak jsme již viděli, predikce větve se někdy strašně pokazí - v nejhorším případě se musíte vrátit a skutečně počkat na načtení paměti, což bude trvat věčně (jinými slovy: selhání predikce větve je špatné, paměť zatížení po selhání predikce větve je prostě hrozné!).
Naštěstí pro nás, pokud je vzor přístupu do paměti předvídatelný, procesor jej načte do své rychlé mezipaměti a vše je v pořádku.
První věc, kterou musíme vědět, je, co je malé? Zatímco menší je obecně lepší, pravidlem je držet se vyhledávacích tabulek o velikosti <= 4096 bajtů. Jako horní limit: pokud je vaše vyhledávací tabulka větší než 64 kB, pravděpodobně stojí za to ji znovu zvážit.
Sestavení stolu
Takže jsme zjistili, že můžeme vytvořit malý stůl. Další věcí je získat vyhledávací funkci na místě. Vyhledávací funkce jsou obvykle malé funkce, které používají několik základních celočíselných operací (and, or, xor, shift, add, remove and probably multily). Chcete, aby váš vstup byl přeložen vyhledávací funkcí na jakýsi „jedinečný klíč“ v tabulce, který vám pak jednoduše dá odpověď na veškerou práci, kterou jste chtěli udělat.
V tomto případě:> = 128 znamená, že si můžeme hodnotu ponechat, <128 znamená, že se jí zbavíme. Nejjednodušší způsob, jak toho dosáhnout, je použití znaku „AND“: pokud ho zachováme, použijeme AND s funkcí 7FFFFFFF; pokud se toho chceme zbavit, my A to s 0. Všimněte si také, že 128 je mocnina 2 - takže můžeme pokračovat a vytvořit tabulku celých čísel 32768/128 a naplnit ji jednou nulou a spoustou 7FFFFFFFF.
Spravované jazyky
Možná se divíte, proč to ve spravovaných jazycích funguje dobře. Koneckonců, spravované jazyky kontrolují hranice polí pomocí větve, aby zajistily, že se nezkazíte ...
No, ne tak úplně ... :-)
Na eliminaci této větve pro spravované jazyky se pracovalo docela dost. Například:
for (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
dlouhý součet = 0;
pro (int i = 0; i <100000; ++ i)
{
// Primární smyčka
pro (int j = 0; j  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "již seřazeno");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "zamícháno");
}
Alespoň tento jev je skutečný s tímto kompilátorem, standardní knihovnou a nastavením optimalizátoru. Různé implementace mohou a mohou dávat různé odpovědi. Ve skutečnosti někdo provedl systematičtější studii (rychlé vyhledávání na webu ji najde) a většina implementací tento efekt ukazuje.
Jedním z důvodů je predikce větve: klíčová operace v algoritmu řazení je „if (v [i]  = 128. To znamená, že můžeme snadno extrahovat jediný bit, který nám řekne, zda chceme hodnotu nebo ne: posunutím data vpravo 7 bitů, zbývá nám 0 bitů nebo 1 bit, a chceme přidat hodnotu pouze v případě, že máme 1 bit. Pojďme tento bit nazvat „rozhodovacím bitem“.
Použitím hodnoty 0/1 rozhodovacího bitu jako indexu do pole můžeme vytvořit kód, který bude stejně rychlý bez ohledu na to, zda jsou data tříděna nebo ne. Náš kód vždy přidá hodnotu, ale když je rozhodovací bit 0, přidáme hodnotu někam, o co se nestaráme. Tady je kód:
// Test
clock_t start = clock ();
long long a [] = {0, 0};
dlouhá dlouhá suma;
pro (nepodepsané i = 0; i <100000; ++ i)
{
// Primární smyčka
for (unsigned c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
suma = a [1];
Tento kód zbytečně polovinu přidává, ale nikdy nemá selhání predikce větve. Je to neuvěřitelně rychlejší na náhodných datech než ve verzi se skutečným příkazem if.
Ale v mém testování byla explicitní vyhledávací tabulka o něco rychlejší, pravděpodobně proto, že indexování do vyhledávací tabulky bylo o něco rychlejší než posunutí bitů. To ukazuje, jak můj kód nastavuje a používá vyhledávací tabulku (v kódu se nápaditě nazývá lut pro „LookUp Table“). Tady je kód C ++:
// Deklarovat a poté vyplnit vyhledávací tabulku
int lut [256];
pro (nepodepsané c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Po vyhledání použijte vyhledávací tabulku
pro (nepodepsané i = 0; i <100000; ++ i)
{
// Primární smyčka
for (unsigned c = 0; c >)
uzel = uzel-> pLeft;
jiný
uzel = uzel-> pRight;
tato knihovna by udělala něco jako:
i = (x );
uzel = uzel-> odkaz [i];
Je to pěkné řešení a možná to bude fungovat.
|
Vysoce aktivní otázka. Získejte 10 reputace, abyste mohli odpovědět na tuto otázku. Požadavek na reputaci pomáhá chránit tuto otázku před spamem a neodpovědností.
Toto není odpověď, kterou hledáte? Přečtěte si další otázky týkající se značek java c ++ optimalizace výkonu větve-predikce nebo položte vlastní otázku.